/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 */
/*
计算单链表的长度；
p指针作为工作指针，p每走一步，就将单链表的结点入栈
如果长度是奇数个，p多走一步
开始出栈，每出栈一个就判断栈顶元素是否和P所指的结点值一样，
如果一样，弹栈，p=p->next
知道遍历到链表尾部
如果最后栈中为空说明链表是回文结构
*/

class Solution {
public:
    /**
     * 
     * @param head ListNode类 the head
     * @return bool布尔型
     */
    bool isPail(ListNode* head) {
        // write code here
        int len=0;
        auto p=head;
        while(p)
        {
            len++;
            p=p->next;
        }
        if(len==1)
            return true;
        p=head;
        stack<int>s;
        int i;
        for(i=0;i<len/2;i++)
        {
            s.push(p->val);
            p=p->next;
        }
        // 2 3 4 3 2
        if(len%2==1) p=p->next;
        while(p!=nullptr&&s.top()==p->val) 
        {
            s.pop();
            p=p->next;
        }
        if(s.empty())
            return true;
        else
            return false;
    }
};